/// @tags: Bitset Matrix
#include <algorithm>
#include <bitset>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <queue>
#define rint register int

using std::cin;
using std::cout;

namespace BlueQuantum {

typedef long long ll;

constexpr int MAXN = 153, INF = 0x3f3f3f3f;

int n;
int d[MAXN];

struct Edge {
  int u, v;
  ll w;
  inline bool operator<(const Edge &rhs) const { return w < rhs.w; }
} e[MAXN];

struct Matrix {
  typedef std::bitset<MAXN> bitset;

  bitset a[MAXN];

  inline Matrix(bool x = false) {
    for (int i = 0; i < n; ++i)
      for (int j = 0; j < n; ++j) a[i][j] = i == j ? x : false;
  }

  inline bitset &operator[](int index) { return a[index]; }
  inline const bitset &operator[](int index) const { return a[index]; }

  inline Matrix operator*(const Matrix &rhs) const {
    Matrix res;
    for (int i = 0; i < n; ++i)
      for (int k = 0; k < n; ++k)
        if (a[i][k]) res[i] |= rhs[k];
    return res;
  }

  inline Matrix operator^(ll exp) const {
    Matrix res(1), base(*this);
    for (; exp; exp >>= 1, base = base * base)
      if (exp & 1) res = res * base;
    return res;
  }
} A, T;

inline void bfs() {
  static std::queue<int> q;
  memset(d, INF, sizeof(d));
  for (int i = 0; i < n; ++i)
    if (A[0][i]) q.emplace(i), d[i] = 0;
  while (!q.empty()) {
    int x = q.front();
    q.pop();
    for (int v = 0; v < n; ++v)
      if (T[x][v] && d[v] == INF) {
        d[v] = d[x] + 1;
        q.emplace(v);
      }
  }
}

inline int main() {
  int m;
  cin >> n >> m;
  for (int i = 1; i <= m; ++i) cin >> e[i].u >> e[i].v >> e[i].w;
  std::sort(e + 1, e + m + 1);
  A[0][0] = true;
  int ans = d[n - 1] = INF, t = 0;
  for (int i = 1; i <= m; ++i) {
    if (ans < e[i].w) break;
    int dt = e[i].w - t;
    t = e[i].w;
    A = A * (T ^ dt);
    T[e[i].u - 1][e[i].v - 1] = true;
    if (i == m || e[i + 1].w != e[i].w) bfs();
    ans = std::min(ans, t + d[n - 1]);
  }
  ans == INF ? cout << "Impossible" : cout << ans;
  return 0;
}

}  // namespace BlueQuantum

int main() {
#ifndef ONLINE_JUDGE
#ifdef LOCAL
  freopen("/tmp/CodeTmp/testdata.in", "r", stdin);
  freopen("/tmp/CodeTmp/testdata.out", "w", stdout);
#else
  freopen("CF576D Flights for Regular Customers.in", "r", stdin);
  freopen("CF576D Flights for Regular Customers.out", "w", stdout);
#endif
#endif

  std::ios::sync_with_stdio(false), cin.tie(NULL), cout.tie(NULL);
  return BlueQuantum::main();
}
